#include <cstring>
#include <iostream>
#include <limits.h>
using namespace std;

const int M = 10;
int d[M][M], n, minDis = INT_MAX; // d数组存储各个城市之间的距离，n表示城市个数，minDis表示最短距离(初始化为极大)
int visited[M];                  // visited数组记录每个城市是否已经被访问过

void backtrack(int cur, int curDis, int count)
{ // cur表示当前城市编号，curDis表示当前距离，count表示已经访问的城市个数
    if (count == n && d[cur][0] != -1)
    {                                             // 所有城市都已经被访问到且返回起点是可行路径
        minDis = min(minDis, curDis + d[cur][0]); // 更新最短路径长度
        return;
    }
    if (curDis >= minDis)
    { // 如果当前路径长度已经大于等于当前最小路径长度，剪枝
        return;
    }
    for (int i = 1; i < n; i++)
    { // 从第二个城市开始遍历，因为第一个城市即起点在递归中已经固定
        if (visited[i] == 0 && d[cur][i] != -1)
        {                                                // 如果该城市未被访问过且与当前城市有边相连
            visited[i] = 1;                           // 标记该城市已经被访问过
            backtrack(i, curDis + d[cur][i], count + 1); // 继续递归搜索
            visited[i] = 0;                          // 回溯
        }
    }
}

int main()
{
    cin >> n;
    // 无向图输入距离矩阵
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> d[i][j];
        }
    }
    memset(visited, 0, sizeof(visited)); // 初始化visited数组
    visited[0] = 1;                       // 起点即城市1已经被访问过
    backtrack(0, 0, 1);                      // 从城市1开始遍历
    cout << "最短路径长度：" << minDis << endl;
    return 0;
}
/*
输入：
4
0 30 6 4
30 0 5 10
6 5 0 20
4 10 20 0

输出：
25

对于这个测试用例，共有4个城市，距离矩阵如上所示。按照回溯法的思路，从城市1开始遍历，遍历过程如下：

(1) 1->2->3->4->1，路径长度为30+5+20+4=59；
(2) 1->2->4->3->1，路径长度为30+10+20+6=66；
(3) 1->3->2->4->1，路径长度为6+5+10+4=25（最短路径）；
(4) 1->3->4->2->1，路径长度为6+20+10+30=66；
(5) 1->4->2->3->1，路径长度为4+10+5+6=25（最短路径）；
(6) 1->4->3->2->1，路径长度为4+20+5+30=59；

因此，最短路径为1->3->2->4->1或1->4->2->3->1，路径长度均为25。
*/
